#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//96.48%
class Solution0
{
  public:
	void sortColors(vector<int> &nums)
	{
		sort(nums.begin(), nums.end());
	}
};
//96.48%
class Solution1
{
  public:
	void sortColors(vector<int> &nums)
	{
		int a = 0, b = 0, c = 0;
		for (int i = 0; i < nums.size(); i++)
		{
			switch (nums[i])
			{
			case 0:
				a++;
				break;
			case 1:
				b++;
				break;
			case 2:
				c++;
				break;
			}
		}
		for (int i = 0; i < a; i++)
		{
			nums[i] = 0;
		}
		for (int i = a; i < a + b; i++)
		{
			nums[i] = 1;
		}
		for (int i = a + b; i < a + b + c; i++)
		{
			nums[i] = 2;
		}
	}
};
//13.04%
class Solution2
{
  public:
	void sortColors(vector<int> &nums)
	{
		int arr[3] = {0, 0, 0};
		for (int i = 0; i < nums.size(); i++)
		{
			arr[nums[i]]++;
		}
		for (int i = 0; i < arr[0]; i++)
		{
			nums[i] = 0;
		}
		for (int i = arr[0]; i < arr[0] + arr[1]; i++)
		{
			nums[i] = 1;
		}
		for (int i = arr[0] + arr[1]; i < arr[0] + arr[1] + arr[2]; i++)
		{
			nums[i] = 2;
		}
	}
};
//96.48%
class Solution3
{
  public:
	void sortColors(vector<int> &nums)
	{
		int a = 0, b = 0, c = 0;
		int l = nums.size();
		while (l--)
		{
			switch (nums[l])
			{
			case 0:
				a++;
				break;
			case 1:
				b++;
				break;
			case 2:
				c++;
				break;
			}
		}
		int index = 0;
		while (a--)
		{
			nums[index++] = 0;
		}
		while (b--)
		{
			nums[index++] = 1;
		}
		while (c--)
		{
			nums[index++] = 2;
		}
	}
};
// 100.00 %
class Solution
{
  public:
	void sortColors(vector<int> &nums)
	{
		int zero = -1, two = nums.size(), i = 0;
		while (i < two)
		{
			switch (nums[i])
			{
			case 0:
				nums[++zero] = 0;
				if (i != zero)
					nums[i] = 1;
				i++;
				break;
			case 1:
				i++;
				break;
			case 2:
				nums[i] = nums[two - 1];
				nums[--two] = 2;
				break;
			}
		}
	}
};

int main()
{
	int nums[6] = {2, 0, 2, 1, 1, 0};
	int len = sizeof(nums) / sizeof(int);
	vector<int> myVector(nums, nums + len);
	Solution().sortColors(myVector);
	for (int i = 0; i < len - 1; i++)
	{
		cout << myVector[i] << " ";
	}
	cout << myVector[len - 1] << endl;
	return 0;
}
